package ai;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Random;


/**
 * The puzzle state is represent by this class. The puzzle property indicate 
 * board spaces, which are numbered from the the first line on the top left to right
 * and then the second line following numbering for each board space, an so on until
 * last integer is assigned to the space in the bottom right of the board.
 * 012
 * 345
 * 678
 *  
 * @author bernard
 *
 */
public class State {

	private static int [][] PROXIMITY_MATIX = 
	{	{1,3},		// 0
		{0,2,4},	// 1
		{1,5},		// 2
		{0,4,6},	// 3
		{1,3,5,7},	// 4
		{2,4,8},	// 5
		{3,7},		// 6 
		{4,6,8},	// 7
		{5,7}		// 8
	};
	
	public final static int SIZE_PUZZLE=9;
	private int[] puzzle = new int[SIZE_PUZZLE];
	
	public State(int [] puzzle) throws Exception{
		if (SIZE_PUZZLE == puzzle.length){
			this.puzzle = puzzle;
			return;
		}
		throw new Exception("To create a state an int array of 9 element should be provided");
	}

	
	/**
	 * Create State by applying action the the passed state and generating other state.
	 * @param puzzle  representation of the puzzle int array of 9 elemnts.
	 * @param act Valid action to move pieces one piece to adjacent empty space.
	 * @throws Exception
	 */
	public State(int [] puzzle, Action act) throws Exception{
		if (SIZE_PUZZLE == puzzle.length){
			this.puzzle = puzzle;
			move(act.initPos, act.destPos);
		}
		throw new Exception("To create a state an int array of 9 element should be provided");
	}
	
	/**
	 * Move to puzzle pice indicated by PuzzlePlace. It validates there is an adjacent empty place
	 * and move its to it.
	 * @param puzzlePlace
	 * @throws Exception
	 */
	public void move(int puzzlePlace) throws Exception{
		if (puzzle[puzzlePlace] != 0){
			int newPlace = whereIsAdjacentZero(puzzlePlace);
			puzzle[newPlace] = puzzle[puzzlePlace];
			puzzle[puzzlePlace] = 0;
		}
		throw new Exception("Empty place can't move");
	}
	
	
	/**
	 * Move pices from initPos to destPos. Validates destPos is empty(equeal to zero). 
	 * @param initPos initail position
	 * @param destPos destiny position
	 */
	public void move(int initPos,int destPos){
		assert(puzzle[destPos] == 0);
		puzzle[destPos] = puzzle[initPos];
		puzzle[initPos] = 0;
	}
	
	/**
	 * Retrieve the puzzle space where the 0 is allocated.
	 * @return   number or puzzle space. It's range is from 0 to 8.
	 * @throws Exception
	 */
	public int whereIsBlank() throws Exception{
		assert(null != this.puzzle);		
		for(int i = 0 ; i< State.SIZE_PUZZLE ; i++){
			if (puzzle[i] == 0 ){
				return i;
			}
		}
		throw  new Exception("There was no empty block. A cero was expected.");
	}
	
	/**
	 * Given a position returns a int indicating where is 
	 * the zero next to the puzzle space indicated by parameter position 
	 * @param position  puzzle space  used as reference to find blank space
	 * @return  if no adjacent zero is found then -1 is retriever otherwise
	 * 			it returns an int indicating the position where the zero is
	 * 			from 0 to 8.
	 */
	public int whereIsAdjacentZero(int position){
		int result = -1;
		int [] adjacentPlaces = PROXIMITY_MATIX[position];
		
		for (int i = 0 ; i < adjacentPlaces.length ; i++){
			if ( 0 == adjacentPlaces[i] ){
				return i;
			}
		}
		return result;
	}
	
	/**
	 * Returns which position are adjacent to certain puzzle position.
	 * @param position puzzle position can be from 0 to 8.
	 * @return Array with adjacent positions
	 */
	public int[]  returnAdjacents(int position){
		if (0 > position || 8 > position ){
			throw new Error("Invalid position");
		}
		return PROXIMITY_MATIX[position];
	}
	
	public boolean equals(Object  sts) {
		if (null == sts){
			return false;			
		}
		
		if (! (sts instanceof State)){
			return false;
		}
				
		int [] stateA = ((State)sts).getPuzzle();
		
		if (null == stateA){
			return false;
		}
		
		if (stateA.length != this.puzzle.length){
			return false;
		}
		
		for (int i=0; i <this.puzzle.length; i++){
			if ( this.puzzle[i] != stateA[i] ){
				return false;
			}
		}
		
		return true;
	}
	
	@Override 
	public int hashCode(){
		int sum = 0;
		sum += puzzle[0]*2;
		sum += puzzle[1]*3;
		sum += puzzle[2]*7;
		sum += puzzle[3]*11;
		sum += puzzle[4]*13;
		sum += puzzle[5]*19;
		sum += puzzle[6]*23;
		sum += puzzle[7]*29;
		sum += puzzle[8]*31;
		return sum;
	}
	
	public String toString(){
		int [] puzzle = this.puzzle;
		String result = new String();
		for (int i : puzzle){
			result = result + " " + Integer.toString(i);
		}
		return result;
	}
	

	public void setPuzzle(int[] puzzle) throws Exception {
		if (puzzle.length != SIZE_PUZZLE){
			throw new Exception("Puzzle size must be 9");
		}
		this.puzzle = puzzle;
	}

	public int[] getPuzzle() {
		return puzzle;
	}
	
	
	/**
	 * Alter actual puzzle to get another state.
	 * @throws Exception
	 */
	public void shuffle() throws Exception{
		int [] newPuzzle = new int[SIZE_PUZZLE];
		
		LinkedList<Integer> numbersList = new LinkedList<Integer>();
		
		//Add all elements to numbersList
		for (int i = 0; i<puzzle.length ; i++){
			numbersList.add(new Integer(puzzle[i]));
		}

		int position;
		int newPosCounter = 0;
		Random generator = new Random();
		while(numbersList.size() > 0){
			position = generator.nextInt(numbersList.size());
			newPuzzle[newPosCounter] = numbersList.remove(position);
			newPosCounter++;
		}
		
		this.puzzle = newPuzzle;
	}
	
	/**
	 * Alter actual puzzle leaving i pieces in the same place
	 * @param pnumPicesSamePlace  number of places that will hold the same value
	 * @throws Exception
	 */
	public void shuffle(int numPiccesDiffPlace) throws Exception{
		
		//take n random positions and copy them.
		if (numPiccesDiffPlace > SIZE_PUZZLE){
			throw new Exception("The puzzle only have " + SIZE_PUZZLE +" pieces.");
		}
		else if(numPiccesDiffPlace <= 1 ){
			throw new Exception("Parameter should be equeal or bigger than 1.");
		}
		
		int numPicesSamePlace = SIZE_PUZZLE-numPiccesDiffPlace;
		
		
		//create new array with all initialized in -1.
		int [] newPuzzle = new int[SIZE_PUZZLE];
		for (int i = 0; i<newPuzzle.length ; i++){
			newPuzzle[i] = -1;
		}
		
		LinkedList<Integer> positionsWillBeSame = new LinkedList<Integer>();
		LinkedList<Integer> avilablePositions = new LinkedList<Integer>();
		
		//Generates a list of all avialable positions
		for(int i = 0; i<SIZE_PUZZLE;i++){
			avilablePositions.add((Integer) i);
		}
		
		int position;
		Random generator = new Random();
		
		//generates a random list of position that will hold the same value
		for(int i = 0 ; i < numPicesSamePlace ;i++){
			position = generator.nextInt(avilablePositions.size());
			positionsWillBeSame.add( avilablePositions.remove(position) );
		}
		
//		System.out.println("Same value: " + positionsWillBeSame);
//		System.out.println("Diff value: " + avilablePositions);
		
		
		//manipulate states to get shuffle uled
		if(avilablePositions.size()>0){
			if (numPiccesDiffPlace > 5 ){  //Change magic number 5
				State bkState = new State(puzzle);
				int entropy;
				while(true){
					this.shuffle();
					entropy = this.calculateEntropy(bkState);
					if (entropy == numPiccesDiffPlace){
						return;
					}
				}
				
			}
			avilablePositions.addLast(avilablePositions.pop()); //TODO: Randomize a little bit more this. ensure that every element is assigned to a different element that before
		}
		
		//Copy values that will be the same
		for (Integer item : positionsWillBeSame){
			newPuzzle[item] = puzzle[item];
		}
		
		int newValue = 0;
		for (int i = 0 ; i<newPuzzle.length ; i++){
			if (newPuzzle[i] == -1){
				newValue = avilablePositions.pop();
				newPuzzle[i] = puzzle[newValue];
			}
		}
				
		//take the rest of the positions
		this.puzzle = newPuzzle;
	}
	
	
	/**
	 * Compare current state with other and measure the entropy
	 * among current state and the passed one
	 * @param a
	 * @return
	 */
	public int calculateEntropy(State a) {
		int count = 0;
		
		int [] puzzA = a.getPuzzle();
		int [] puzzB = puzzle;
		
		for(int i=0; i< SIZE_PUZZLE; i++){
			if (puzzA[i] != puzzB[i]){
				count++;
			}
		}
		return count;
	}
	
	/**
	 * Returns the a list of position in puzzle that are different from state other
	 * @param other State to compare
	 * @return
	 */
	public List<Integer> diff(State other){
		List<Integer> differences = new ArrayList<Integer>();
		
		int [] otherPuzz = other.getPuzzle();
		
		for(int i=0; i< SIZE_PUZZLE; i++){
			if (otherPuzz[i] != puzzle[i]){
				differences.add(puzzle[i]);
			}
		}
		return differences;
	}
	
}
